package zisu.algorithm.algorithm.MaxHeap;

import sun.reflect.generics.tree.Tree;
import zisu.algorithm.algorithm.MaxHeap.priorityQueue.PriorityQueue;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;

//给定一个非空的整数数组，返回其中出现频率前k高的元素。给定数组[1,1,1,2,2,3] ,和k=2,返回[1,2]
public class Solution {
    // 因为Freq 需要可比较  所以要实现Comparable<Freq> 接口。
    private class Freq implements Comparable<Freq>{
        int e,freq;

        public Freq(int e ,int freq){
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq another) {
            // 如果传进来的数，比本身的数大。
            if(this.e < another.e){
                return 1;
            }else if(this.e > another.e){
                return -1;
            }else {
                return 0;
            }

        }
    }
    public List<Integer> topKFrequent(int[] nums,int k) throws Exception {
        TreeMap<Integer,Integer> map = new TreeMap<>();
        for(int num:nums){
            if(map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else {
                map.put(num,1);
            }
        }


        PriorityQueue<Freq> freqPriorityQueue = new PriorityQueue<>();
        // map.keySet() 是 K(键) 的集合
        for (int i : map.keySet()){
            if(freqPriorityQueue.getSize() < k){
                freqPriorityQueue.enQueue(new Freq(i,map.get(i)));
            }else if(freqPriorityQueue.getFront().freq < map.get(i)){
                Freq freq = freqPriorityQueue.deQueue();
                freqPriorityQueue.enQueue(new Freq(i,map.get(i)));
            }
        }
        LinkedList<Integer> linkedList = new LinkedList<>();
        while (!freqPriorityQueue.isEmpty()){
            linkedList.add(freqPriorityQueue.deQueue().e);
        }
        return linkedList;
    }
}
